package com.lwg.datastructure.dynamicPrograming;

/**
 * @author: lwg
 * @Date: 2022/2/20 22:31
 * @Description: 环形最大子数组和
 * <p>
 * 分析：
 * 1. 情况：最大数组和在数组中间，最大数组和在数组的两端
 * 2. 子数组和最大的两个分析：
 * 2.1 最大数组和两端的肯定是正数
 * 2.2 紧挨着最大数组和一定是负数
 * 3. 此时如果我们求出最小数组和是多少，那么就得到了最大数组和是多少！！ 此时就利用 (整个数组和-最小数组和=最大数组和)
 * 为什么呢？(最小数组和的情况)
 * 3.1 最小数组和一定是负数 ，如果是正数，就需要合并到最大数组和内，保证最大数组和最大
 * 3.2 从左到右累加的数，从一开始就是负数，因为开始是正数的话，就不会累加到其中，但中间是正数的情况则会出现，就算出现也得满足第一条
 * <p>
 * 分析：
 * 1. 情况：最大数组和在数组中间，最大数组和在数组的两端
 * 2. 子数组和最大的两个分析：
 * 2.1 最大数组和两端的肯定是正数
 * 2.2 紧挨着最大数组和一定是负数
 * 3. 此时如果我们求出最小数组和是多少，那么就得到了最大数组和是多少！！ 此时就利用 (整个数组和-最小数组和=最大数组和)
 * 为什么呢？(最小数组和的情况)
 * 3.1 最小数组和一定是负数 ，如果是正数，就需要合并到最大数组和内，保证最大数组和最大
 * 3.2 从左到右累加的数，从一开始就是负数，因为开始是正数的话，就不会累加到其中，但中间是正数的情况则会出现，就算出现也得满足第一条
 * <p>
 * 分析：
 * 1. 情况：最大数组和在数组中间，最大数组和在数组的两端
 * 2. 子数组和最大的两个分析：
 * 2.1 最大数组和两端的肯定是正数
 * 2.2 紧挨着最大数组和一定是负数
 * 3. 此时如果我们求出最小数组和是多少，那么就得到了最大数组和是多少！！ 此时就利用 (整个数组和-最小数组和=最大数组和)
 * 为什么呢？(最小数组和的情况)
 * 3.1 最小数组和一定是负数 ，如果是正数，就需要合并到最大数组和内，保证最大数组和最大
 * 3.2 从左到右累加的数，从一开始就是负数，因为开始是正数的话，就不会累加到其中，但中间是正数的情况则会出现，就算出现也得满足第一条
 * <p>
 * 分析：
 * 1. 情况：最大数组和在数组中间，最大数组和在数组的两端
 * 2. 子数组和最大的两个分析：
 * 2.1 最大数组和两端的肯定是正数
 * 2.2 紧挨着最大数组和一定是负数
 * 3. 此时如果我们求出最小数组和是多少，那么就得到了最大数组和是多少！！ 此时就利用 (整个数组和-最小数组和=最大数组和)
 * 为什么呢？(最小数组和的情况)
 * 3.1 最小数组和一定是负数 ，如果是正数，就需要合并到最大数组和内，保证最大数组和最大
 * 3.2 从左到右累加的数，从一开始就是负数，因为开始是正数的话，就不会累加到其中，但中间是正数的情况则会出现，就算出现也得满足第一条
 * <p>
 * 分析：
 * 1. 情况：最大数组和在数组中间，最大数组和在数组的两端
 * 2. 子数组和最大的两个分析：
 * 2.1 最大数组和两端的肯定是正数
 * 2.2 紧挨着最大数组和一定是负数
 * 3. 此时如果我们求出最小数组和是多少，那么就得到了最大数组和是多少！！ 此时就利用 (整个数组和-最小数组和=最大数组和)
 * 为什么呢？(最小数组和的情况)
 * 3.1 最小数组和一定是负数 ，如果是正数，就需要合并到最大数组和内，保证最大数组和最大
 * 3.2 从左到右累加的数，从一开始就是负数，因为开始是正数的话，就不会累加到其中，但中间是正数的情况则会出现，就算出现也得满足第一条
 * <p>
 * 分析：
 * 1. 情况：最大数组和在数组中间，最大数组和在数组的两端
 * 2. 子数组和最大的两个分析：
 * 2.1 最大数组和两端的肯定是正数
 * 2.2 紧挨着最大数组和一定是负数
 * 3. 此时如果我们求出最小数组和是多少，那么就得到了最大数组和是多少！！ 此时就利用 (整个数组和-最小数组和=最大数组和)
 * 为什么呢？(最小数组和的情况)
 * 3.1 最小数组和一定是负数 ，如果是正数，就需要合并到最大数组和内，保证最大数组和最大
 * 3.2 从左到右累加的数，从一开始就是负数，因为开始是正数的话，就不会累加到其中，但中间是正数的情况则会出现，就算出现也得满足第一条
 * <p>
 * 分析：
 * 1. 情况：最大数组和在数组中间，最大数组和在数组的两端
 * 2. 子数组和最大的两个分析：
 * 2.1 最大数组和两端的肯定是正数
 * 2.2 紧挨着最大数组和一定是负数
 * 3. 此时如果我们求出最小数组和是多少，那么就得到了最大数组和是多少！！ 此时就利用 (整个数组和-最小数组和=最大数组和)
 * 为什么呢？(最小数组和的情况)
 * 3.1 最小数组和一定是负数 ，如果是正数，就需要合并到最大数组和内，保证最大数组和最大
 * 3.2 从左到右累加的数，从一开始就是负数，因为开始是正数的话，就不会累加到其中，但中间是正数的情况则会出现，就算出现也得满足第一条
 * <p>
 * 分析：
 * 1. 情况：最大数组和在数组中间，最大数组和在数组的两端
 * 2. 子数组和最大的两个分析：
 * 2.1 最大数组和两端的肯定是正数
 * 2.2 紧挨着最大数组和一定是负数
 * 3. 此时如果我们求出最小数组和是多少，那么就得到了最大数组和是多少！！ 此时就利用 (整个数组和-最小数组和=最大数组和)
 * 为什么呢？(最小数组和的情况)
 * 3.1 最小数组和一定是负数 ，如果是正数，就需要合并到最大数组和内，保证最大数组和最大
 * 3.2 从左到右累加的数，从一开始就是负数，因为开始是正数的话，就不会累加到其中，但中间是正数的情况则会出现，就算出现也得满足第一条
 * <p>
 * 分析：
 * 1. 情况：最大数组和在数组中间，最大数组和在数组的两端
 * 2. 子数组和最大的两个分析：
 * 2.1 最大数组和两端的肯定是正数
 * 2.2 紧挨着最大数组和一定是负数
 * 3. 此时如果我们求出最小数组和是多少，那么就得到了最大数组和是多少！！ 此时就利用 (整个数组和-最小数组和=最大数组和)
 * 为什么呢？(最小数组和的情况)
 * 3.1 最小数组和一定是负数 ，如果是正数，就需要合并到最大数组和内，保证最大数组和最大
 * 3.2 从左到右累加的数，从一开始就是负数，因为开始是正数的话，就不会累加到其中，但中间是正数的情况则会出现，就算出现也得满足第一条
 * <p>
 * 分析：
 * 1. 情况：最大数组和在数组中间，最大数组和在数组的两端
 * 2. 子数组和最大的两个分析：
 * 2.1 最大数组和两端的肯定是正数
 * 2.2 紧挨着最大数组和一定是负数
 * 3. 此时如果我们求出最小数组和是多少，那么就得到了最大数组和是多少！！ 此时就利用 (整个数组和-最小数组和=最大数组和)
 * 为什么呢？(最小数组和的情况)
 * 3.1 最小数组和一定是负数 ，如果是正数，就需要合并到最大数组和内，保证最大数组和最大
 * 3.2 从左到右累加的数，从一开始就是负数，因为开始是正数的话，就不会累加到其中，但中间是正数的情况则会出现，就算出现也得满足第一条
 */

/**
 * 分析：
 *   1. 情况：最大数组和在数组中间，最大数组和在数组的两端
 *   2. 子数组和最大的两个分析：
 *      2.1 最大数组和两端的肯定是正数
 *      2.2 紧挨着最大数组和一定是负数
 *   3. 此时如果我们求出最小数组和是多少，那么就得到了最大数组和是多少！！ 此时就利用 (整个数组和-最小数组和=最大数组和)
 *   为什么呢？(最小数组和的情况)
 *      3.1 最小数组和一定是负数 ，如果是正数，就需要合并到最大数组和内，保证最大数组和最大
 *      3.2 从左到右累加的数，从一开始就是负数，因为开始是正数的话，就不会累加到其中，但中间是正数的情况则会出现，就算出现也得满足第一条
 */

/**
 * for (整个数组) {
 *     53题逻辑找，最大子数组和；
 *     53题逻辑找，最小子数组和；
 *     累加整个数组的和；
 * }
 * if (最大数组的和是不是负数)
 *     return 最大数组的和； // 存在整个数组一个正数都不存在的情况
 * else {
 *     if (如果是53题这样的状况)
 *         return 最大数组的和
 *     else // 环形数组
 *         return 整个数组的和 - 最小数组的和；
 */
public class CircleMaxChuldNumsSum {

    public int maxSubarraySumCircular(int[] nums) {
        int preMax = 0;
        int maxSum = nums[0];
        int preMin = 0;
        int minSum = nums[0];
        int totalSum = 0;
        //利用非环形链表的逻辑得到最大数组和，最小数组和
        for (int num : nums) {
            preMax = Math.max(preMax + num, num);
            maxSum = Math.max(preMax, maxSum);
            preMin = Math.min(preMin + num, num);
            minSum = Math.min(preMin, minSum);
            totalSum += num;
        }
        return maxSum > 0 ? Math.max(maxSum, totalSum - minSum) : maxSum;
    }
}
